/**
 * 剑指 Offer 12. 矩阵中的路径（与 79 同）
 * https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/
 */
public class Solutions_Offer_12 {
    public static void main(String[] args) {
        char[][] board = {{'A', 'B', 'C', 'E'},
                          {'S', 'F', 'C', 'S'},
                          {'A', 'D', 'E', 'E'}};
//        String word = "ABCCED";  // output: true
//        String word = "BFCE";  // output: true
        String word = "ABFB";  // output: false

//        char[][] board = {{'a', 'b'},
//                          {'c', 'd'}};
//        String word = "abcd";  // output: false

//        char[][] board = {{'a'}};
//        String word = "a";  // output: true

        boolean result = exist(board, word);
        System.out.println(result);
    }

    public static boolean exist(char[][] board, String word) {
        if (board == null) {
            return word.length() < 1;
        }
        int row = board.length;
        int col = board[0].length;
        char[] sarr = word.toCharArray();
        boolean[][] mark = new boolean[row][col];
        // 上、下、左、右
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == sarr[0]) {
                    // 首字母相同时，判断后续的字母是否相同
                    boolean res = exist_dfs(board, sarr, mark, 0,
                            directions, i, j, row, col);
                    if (res) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public static boolean exist_dfs(char[][] board, char[] sarr, boolean[][] mark,
                                    int index, int[][] directions, int i, int j,
                                    int row, int col) {
        // 结束条件：两字母不相等
        if (index == sarr.length - 1) {
            // 遍历到最后一个字母时，判断是否相等
            return board[i][j] == sarr[index];
        }
        // 结束条件
        if (board[i][j] != sarr[index]) {
            return false;
        }
        // 当前位置标记为已访问
        mark[i][j] = true;
        for (int[] dir : directions) {
            // 以 [i,j] 为原点，向上、下、左、右四个方向上展开，判断是否等于下一个字母
            int x = i + dir[0];
            int y = j + dir[1];
            if (x >= 0 && x < row && y >= 0 && y < col && !mark[x][y]) {
                boolean res = exist_dfs(board, sarr, mark, index + 1,
                        directions, x, y, row, col);
                if (res == true) {
                    // 从 [x,y] 位置，向四个方向上展开后，能够走完 word，return true
                    return true;
                }
            }
        }
        // 结束，说明从该位置向四个方向展开，不能走完 word，取消标记
        mark[i][j] = false;
        return false;
    }
}
